package com.leetcode.offer.chapter2;

/**
 * @author Dennis Li
 * @date 2020/7/11 21:10
 */
public class Fibbonacci_09 {

    public static void main(String[] args) {
        //System.out.println(fibbonacci(4));
        System.out.println(fib(45));
    }

    public static int fib(int n) {
        // 简洁，但是会产生大量的重复数
        if (n <= 1) return n == 1 ? 1 : 0;
        return fib(n - 1) + fib(n - 2);
    }

    public static int fibbonacci(int n) {
        // 推荐做法，空间占用为O(1)常数级别，时间复杂度为O(n)
        if (n <= 1) return n == 1 ? 1 : 0;
        int[] result = {0, 1};
        int temp = 0;
        for (int i = 2; i <= n; i++) {
            temp = result[0] + result[1];
            result[0] = result[1];
            result[1] = temp;
        }
        return temp;
    }


}
